package 双指针系列;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class DetectCycle {
    //hashset大法
    public ListNode detectCycle(ListNode head){

        ListNode cur = head;
        HashSet<ListNode> nodes = new HashSet<>();
        while (cur!=null){
            if(nodes.contains(cur)){
                return cur;
            }
            nodes.add(cur);
            cur = cur.next;
        }
        return null;
    }
    //双指针
    public ListNode detectCycle1(ListNode head){

        ListNode fast = head;
        ListNode slow = head;

        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow){
                ListNode index1 = fast;
                ListNode index2 = head;
                while(index1!=index2){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }

        }

        return null;
    }
}
